import random


class Solution(object):

    def __init__(self, w):
        """
        :type w: List[int]
        """
        self.w = w
        for i in range(1, len(w)):
            self.w[i] += self.w[i - 1]
        self.n = len(w)

    def search(self, value):
        left = 0
        right = self.n - 1
        while left < right:
            mid = (left + right) // 2
            if self.w[mid] >= value:
                right = mid
            else:
                left = mid + 1
        return left

    def pickIndex(self):
        """
        :rtype: int
        """
        rd = random.randint(1, self.w[-1])
        return self.search(rd)


obj = Solution([1, 3])
print(obj.pickIndex())
print(obj.pickIndex())
print(obj.pickIndex())
print(obj.pickIndex())
